package algorithm;

public class leetcode_0416 {
    public boolean canPartition(int[] nums) {
        int sum=0;
        int len=nums.length;
        if(len==1) return false;
        for(int i=0;i<len;++i){
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int [][] dp=new int[len+1][sum/2+1];
        for(int i=1;i<=len;++i){
            for(int j=1;j<sum/2+1;++j){
                if(j>=nums[i-1]) dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
                else dp[i][j]=dp[i-1][j];
            }
        }
        for(int i=0;i<=len;++i){
            if(dp[i][sum/2]==sum/2) return true;
        }
        return false;
    }
}
